#include "pch.h"
#include "OverlayHelper.h"
#include "EffectDesc.h"
#include <random>

namespace Magpie {

static void UnpackAccumulativeOffsetsIntoRanges(
	int baseCodepoint,
	const short* accumulativeOffsets,
	int accumulativeOffsetsCount,
	ImWchar* outRanges
) noexcept {
	for (int n = 0; n < accumulativeOffsetsCount; n++, outRanges += 2) {
		outRanges[0] = outRanges[1] = (ImWchar)(baseCodepoint + accumulativeOffsets[n]);
		baseCodepoint += accumulativeOffsets[n];
	}
	outRanges[0] = 0;
}

const ImWchar* OverlayHelper::GetGlyphRangesChineseSimplifiedOfficial() noexcept {
	// 存储了通用规范汉字表中的一级字表（3500字）以及其他一些常用字。
	// 来自 https://zh.wiktionary.org/wiki/Appendix:%E9%80%9A%E7%94%A8%E8%A7%84%E8%8C%83%E6%B1%89%E5%AD%97%E8%A1%A8
	// 由 CJKCharacterSetForImGui 生成，它位于 tools 文件夹中。
	// (Stored as accumulative offsets from the initial unicode codepoint 0x4E00. This encoding is designed to helps us compact the source code size.)
	static const short accumulativeOffsetsFrom0x4E00[] =
	{
		0,1,2,4,1,1,1,1,2,1,2,1,2,1,2,2,1,1,1,1,1,5,2,1,2,3,1,2,3,2,2,4,1,1,1,2,1,5,2,3,1,2,1,1,1,1,1,2,1,1,2,2,1,4,1,1,1,1,5,10,1,2,11,8,2,1,2,1,2,
		1,2,1,2,1,5,1,6,1,2,1,1,1,2,2,1,1,1,4,8,5,1,1,4,1,1,3,1,2,1,3,2,1,2,1,1,1,10,1,1,5,2,4,2,4,1,4,2,2,2,9,3,2,1,1,6,1,1,1,4,1,1,4,2,4,5,1,4,2,2,
		2,2,7,3,7,1,1,1,1,2,2,4,2,1,4,3,6,10,12,5,4,3,2,14,2,3,3,2,1,1,1,6,1,6,10,4,1,6,5,1,7,1,5,4,8,4,1,1,2,9,19,5,2,4,1,1,5,2,5,20,2,2,9,7,1,11,2,
		9,17,1,8,6,8,27,4,6,9,20,11,13,14,6,23,45,2,2,1,1,1,2,1,2,2,4,3,6,2,6,3,3,3,1,1,3,1,2,1,1,1,1,1,1,2,1,1,3,5,3,1,3,1,5,5,2,2,1,4,4,1,7,3,1,2,
		1,2,1,1,4,5,4,2,3,3,3,2,10,2,3,1,3,9,2,1,3,3,2,1,1,1,2,2,1,1,2,3,1,3,7,1,5,1,1,1,1,2,3,4,4,1,2,3,2,6,1,1,1,1,1,7,1,7,3,4,3,2,15,2,2,1,5,3,13,
		9,19,2,1,1,1,1,2,5,1,1,1,6,1,1,12,4,4,2,2,7,6,7,5,22,4,1,1,5,1,2,13,1,1,2,7,3,7,15,1,1,3,1,2,2,4,1,1,1,4,1,2,1,1,2,1,1,3,2,4,1,1,2,2,1,4,4,1,
		1,2,1,1,2,1,7,3,3,1,3,2,1,9,3,2,5,3,4,2,19,4,2,1,6,1,1,1,1,1,4,3,2,1,1,1,2,5,3,1,1,1,2,1,1,1,1,1,1,1,1,2,1,3,1,1,1,3,1,4,2,1,2,2,1,1,2,1,1,1,
		1,1,2,2,2,4,2,1,1,1,6,1,1,1,2,1,1,1,1,2,3,1,3,1,2,1,2,2,6,2,2,6,5,3,3,1,6,6,11,2,6,1,1,7,7,1,3,1,2,3,1,3,14,1,2,2,5,2,5,5,3,1,3,2,1,1,1,4,1,
		3,6,8,6,1,2,1,1,3,1,4,8,2,5,5,1,2,7,16,4,3,5,2,1,2,13,5,1,2,4,23,3,1,1,4,6,8,4,6,2,3,2,1,14,4,1,10,12,4,4,10,14,9,5,5,23,3,9,18,22,1,2,2,3,2,
		4,41,1,1,36,21,20,5,14,16,1,3,2,2,2,9,3,1,3,6,3,1,5,3,2,23,4,5,8,10,4,2,7,3,4,1,1,1,6,3,1,2,2,1,1,3,2,4,5,8,11,1,1,7,7,9,7,4,5,3,20,1,8,3,17,
		1,25,1,8,4,15,12,3,6,6,5,23,5,3,4,6,13,24,2,14,6,5,1,9,1,24,35,7,1,2,2,3,3,3,11,3,6,2,6,1,4,2,3,8,2,1,1,2,1,1,2,3,3,1,1,1,13,1,1,2,4,2,3,2,1,
		9,2,3,14,1,2,2,1,4,5,1,1,2,1,1,10,1,3,3,12,3,6,11,2,11,4,1,5,1,2,1,6,2,9,3,19,4,2,2,1,3,17,4,3,6,12,5,16,3,17,16,10,2,9,19,8,25,14,1,7,3,29,
		103,4,1,2,1,1,4,2,4,1,2,3,12,8,4,2,2,2,1,1,2,1,3,8,1,1,1,1,1,1,1,2,1,1,1,1,2,4,1,5,3,1,1,1,3,4,1,1,3,2,1,1,1,5,6,1,10,1,1,2,4,3,16,1,1,1,1,3,
		2,3,2,3,1,5,2,3,2,2,2,3,7,3,5,5,3,4,2,2,1,1,1,1,1,1,3,3,1,1,1,3,1,2,4,9,2,1,4,10,2,8,6,2,1,18,2,1,4,14,4,6,5,41,5,2,5,3,11,12,7,6,2,5,14,4,
		31,121,8,16,1,3,1,3,1,1,1,1,2,3,3,1,1,1,3,7,3,1,1,2,1,2,4,4,5,1,2,2,2,1,9,1,6,1,9,1,5,8,7,9,13,16,1,1,2,2,3,1,1,2,5,2,1,3,5,1,3,1,1,2,2,1,2,
		2,1,7,1,6,8,1,1,1,17,1,9,35,1,3,6,2,1,1,6,5,4,2,2,1,3,4,1,5,1,1,8,2,8,1,24,1,2,13,2,5,1,2,1,3,1,8,2,1,4,1,3,1,3,2,1,5,2,5,1,1,8,9,4,9,6,6,2,
		1,6,1,10,1,1,7,7,4,6,4,8,2,1,1,13,4,2,1,1,6,1,3,1,4,2,1,2,5,12,8,8,2,3,2,3,13,2,4,1,3,1,2,1,3,3,6,8,5,4,7,2,9,1,3,3,2,4,3,3,2,8,9,5,1,6,4,7,
		3,1,6,1,1,1,2,2,2,1,3,3,3,8,7,1,6,6,5,5,4,1,3,24,9,4,2,7,13,5,1,8,7,20,3,6,20,22,4,6,2,8,20,34,2,2,2,1,1,1,1,4,2,2,16,9,1,3,8,1,1,6,4,2,1,3,
		1,1,1,4,3,8,4,2,2,1,1,1,1,1,3,3,3,3,2,1,1,4,6,7,1,1,2,1,1,1,2,1,5,1,1,2,1,6,1,5,4,4,3,1,5,2,1,1,1,2,3,1,1,2,2,1,1,2,1,1,1,2,1,3,3,1,2,1,1,1,
		1,3,1,2,2,2,1,3,5,1,1,1,2,1,5,2,5,3,5,4,5,1,1,2,1,1,3,2,1,4,11,3,5,3,1,3,3,1,1,1,1,5,9,1,2,1,1,4,7,8,1,3,1,5,2,6,1,3,3,1,2,6,8,2,3,2,1,1,1,6,
		7,3,15,4,2,1,2,15,2,6,1,3,7,9,3,1,1,3,10,4,1,8,2,14,1,13,10,2,1,3,10,4,15,2,15,1,14,10,1,3,9,6,5,3,1,1,2,5,7,6,3,8,1,4,20,26,47,7,3,2,3,1,6,
		3,4,3,2,8,2,3,4,1,3,6,4,2,2,3,16,4,1,5,6,2,3,3,5,1,2,2,4,2,1,9,4,4,4,6,4,8,9,2,3,1,1,1,1,3,1,4,5,1,3,8,4,6,2,1,4,1,11,1,5,2,1,5,2,13,2,5,8,1,
		6,1,2,5,12,2,6,1,1,4,2,4,4,4,5,10,5,1,23,6,37,4,19,2,2,5,3,2,1,1,8,1,2,2,10,4,2,2,7,2,2,1,1,3,2,3,1,5,3,3,2,1,3,3,5,1,1,1,5,6,3,1,1,4,3,5,2,
		1,14,1,2,3,5,7,5,2,3,2,1,5,1,7,1,4,7,14,11,1,1,1,1,1,8,4,5,7,5,2,1,11,6,2,1,3,4,2,2,3,1,10,9,13,1,1,3,1,5,1,3,2,4,4,1,3,15,2,1,2,1,13,11,4,1,
		17,11,4,1,1,5,2,1,3,13,9,2,2,5,3,3,2,6,14,3,4,5,11,8,1,4,27,3,15,27,29,5,6,2,2,14,1,7,12,12,28,11,34,34,2,9,7,19,20,1,8,16,15,16,28,116,1,1,
		1,4,11,8,4,9,2,3,22,1,1,1,1,1,3,15,2,1,7,6,1,1,11,30,1,2,8,2,4,8,2,3,2,1,4,2,6,10,4,32,2,2,1,7,7,5,1,6,1,5,4,9,1,5,2,14,4,2,1,1,1,1,3,6,6,9,
		4,4,2,5,1,7,9,2,4,2,4,1,1,3,1,3,5,5,1,2,1,1,1,1,5,5,1,2,9,6,3,3,1,1,2,3,2,6,3,2,6,1,1,4,10,7,5,4,3,7,5,8,9,1,1,1,3,4,1,1,3,1,3,1,2,2,6,13,3,
		1,4,6,3,1,10,6,1,3,9,6,2,4,2,1,2,1,1,1,5,1,3,3,11,6,5,1,5,7,9,3,7,3,3,2,4,2,2,10,5,6,4,3,6,3,1,2,1,5,6,3,2,4,2,9,19,2,38,1,4,2,4,7,12,6,8,5,
		7,4,13,4,6,3,6,4,3,3,1,3,1,11,14,4,9,4,1,12,11,6,13,9,17,4,17,1,22,4,6,14,5,18,13,18,63,59,31,2,2,1,5,1,2,4,2,1,10,1,4,4,3,22,1,1,1,10,1,3,5,
		1,6,16,1,2,4,5,2,1,4,2,12,16,1,11,5,12,10,6,22,2,16,6,3,7,15,7,6,5,5,5,6,13,23,18,16,33,36,2,5,4,1,1,1,1,4,10,1,4,13,2,6,1,5,2,9,3,4,1,6,1,
		43,3,7,3,9,6,8,7,7,2,1,11,1,1,2,1,7,4,18,8,5,1,13,1,1,1,2,6,10,1,69,3,2,2,11,5,14,2,4,1,2,5,4,15,3,19,13,22,2,1,3,7,18,17,1,8,29,5,1,17,19,
		36,53,6,1,1,2,16,1,33,2,2,3,6,3,1,2,5,1,1,1,2,2,1,3,10,7,3,5,5,3,9,5,10,4,14,9,2,6,2,1,5,5,7,3,1,3,7,3,2,7,2,3,8,3,3,3,7,8,6,4,5,38,5,2,3,1,
		1,13,6,14,23,21,3,2,1,4,2,2,1,12,3,24,3,14,7,2,2,5,1,1,1,2,2,1,1,3,4,15,1,3,2,4,1,3,2,3,8,2,20,1,8,7,7,1,5,4,1,15,11,6,2,3,5,1,13,11,1,9,4,
		21,2,1,2,1,6,8,28,4,7,1,2,4,2,2,1,5,11,1,2,1,10,1,7,2,4,22,4,4,6,2,5,16,8,14,1,2,30,1,1,3,6,1,7,8,9,1,2,11,3,4,5,11,19,15,10,57,2,2,2,8,14,7,
		1,1,1,5,3,5,10,1,8,1,3,1,10,42,2,2,1,2,1,2,3,3,2,2,4,1,6,7,5,2,1,2,6,1,8,3,2,3,11,2,1,12,6,19,8,1,1,2,7,17,29,2,1,3,5,2,2,1,9,4,1,4,1,1,4,1,
		2,6,26,12,11,3,5,1,1,3,2,8,2,10,6,12,6,3,5,2,11,2,4,16,13,2,4,1,1,1,2,2,5,2,26,2,5,2,21,2,10,8,2,2,4,22,12,14,13,3,6,16,32,17,7,14,38,8,2,12,
		9,5,1,7,5,1,5,4,3,8,5,12,11,1,3,6,1,15,12,15,22,2,5,4,4,63,211,95,2,2,2,1,3,1,1,3,2,1,1,2,2,1,1,1,3,2,4,1,1,1,1,1,2,3,1,1,2,1,1,2,3,1,1,2,1,
		1,1,3,1,4,2,1,3,3,3,1,1,2,1,4,1,2,1,5,1,3,5,5,1,1,1,2,2,3,3,4,5,4,3,4,4,2,22,1,4,2,3,8,7,1,4,4,24,4,6,6,4,3,3,21,4,4,4,15,4,8,9,7,11,1,4,1,2,
		2,7,1,3,5,2,1,1,26,5,3,2,2,3,4,4,1,1,8,4,2,16,25,3,1,2,2,1,10,2,2,1,2,3,1,1,2,1,4,1,4,1,3,2,6,4,1,1,1,2,3,6,2,8,4,2,2,3,6,9,3,3,2,5,5,4,3,1,
		5,1,1,2,3,4,21,2,7,6,12,1,5,4,1,16,9,2,9,1,1,3,1,1,10,5,12,1,1,11,24,2,8,25,7,3,6,1,8,4,5,1,6,1,5,2,10,1,11,2,4,1,4,1,3,14,17,23,1,2,1,7,4,4,
		9,7,7,3,1,8,1,6,1,2,2,2,6,4,10,6,2,2,3,3,4,3,1,6,1,11,8,8,1,1,1,1,4,5,25,4,1,9,1,2,14,3,7,2,2,13,2,1,3,4,4,8,18,34,6,1,5,2,1,3,10,3,2,16,4,9,
		8,1,18,8,1,1,15,7,1,2,1,21,26,4,6,2,8,1,5,4,13,9,14,3,22,6,12,5,20,15,37,2,4,3,7,11,16,1,12,1,42,10,6,3,20,15,5,26,6,1,5,15,23,22,61,1,1,1,9,
		17,14,4,1,2,1,1,8,2,7,2,14,1,6,5,17,7,4,14,2,9,10,16,2,2,6,10,1,2,2,1,4,5,26,12,2,3,2,9,2,7,20,2,13,10,45,6,6,5,46,28,13,30,5,7,1,7,3,2,8,2,
		2,3,3,1,4,7,10,3,7,2,9,6,15,2,4,16,1,3,16,4,11,15,5,1,9,14,2,19,5,53,32,2,5,59,1,2,1,1,2,1,9,17,3,26,137,1,9,211,6,53,1,2,1,3,1,4,1,1,1,2,1,
		3,2,1,1,2,1,1,1,1,1,3,2,2,1,1,3,4,4,2,3,3,1,3,1,3,1,5,1,1,2,2,1,2,1,2,1,2,1,2,1,3,2,2,1,2,2,1,2,1,2,3,7,2,6,1,1,2,2,4,1,4,3,3,10,5,6,14,7,9,
		1,14,1,18,145,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,2,1,1,1,1,1,2,1,2,1,1,1,7,1,2,1,1,4,2,2,2,1,3,2,1,1,1,1,2,5,5,4,1,1,1,10,4,5,1,20,4,
		16,1,10,5,8,1,5,10,2,2,5,4,2,5,4,2,2,3,16,5,19,7,1,7,17,2,4,3,27,6,1,5,15,14,28,1,3,3,8,172,1,1,1,3,2,1,1,4,7,2,2,4,2,1,2,1,7,1,2,3,1,2,2,1,
		2,1,4,5,1,2,5,1,8,4,1,3,1,2,1,2,1,6,2,1,3,4,1,2,1,1,1,1,3,8,1,2,3,7,2,4,3,1,1,1,3,3,1,5,1,2,2,3,3,1,2,1,1,1,2,12,10,3,1,2,4,5,6,2,4,4,12,2,8,
		1,7,10,1,17,2,16,3,4,4,13,6,9,4,3,23,5,16,5,23,48,3,1,5,5,6,6,2,5,2,5,4,2,1,7,8,2,2,7,53,3,2,1,1,1,2,163,532,1,10,6,4,1,1,1,2,3,1,1,2,5,3,2,
		8,3,3,2,2,11,11,1,1,16,5,4,2,2,4,2,1,3,1,3,3,1,4,9,1,7,2,1,1,1,8,1,1,9,2,5,7,9,1,11,20,6,9,105,2,3,1,1,1,2,2,3,1,1,1,1,2,3,1,4,9,2,4,11,19,1,
		1,1,1,5,4,5,1,1,2,3,1,1,3,5,12,1,2,4,1,1,11,1,1,14,1,5,4,1,4,4,1,3,11,15,8,2,1,3,1,1,1,5,3,6,19,2,9,3,1,2,5,2,4,3,2,4,1,14,2,20,6,1,25,4,3,5,
		2,1,1,7,11,2,21,2,19,13,58,2,4,6,2,128,1,1,2,1,1,2,1,1,2,1,2,1,1,1,1,2,7,2,3,1,1,4,1,3,4,42,10,6,1,49,85,8,1,2,1,1,3,1,4,2,3,2,4,1,2,3,2,2,3,
		4,3,15,196,2,1,1,1,2,1,2,3,2,1,2,4,2,2,1,5,3,2,6,3,7,3,4,43,5,59,41,5,1,2,1,10,5,296,5,12,15,8,4,3,13,12,9,9,8,321,2,2,2,1,7,2,4,2,8,2,4,2,4,
		1,5,21,2,10,15,39,21,9,10,3,3,4,23,31,5,13,27,21,47,5,21,6
	};
	static ImWchar baseRanges[] = // not zero-terminated
	{
		0x0020, 0x00FF, // Basic Latin + Latin Supplement
		0x2000, 0x206F, // General Punctuation
		0x3000, 0x30FF, // CJK Symbols and Punctuations, Hiragana, Katakana
		0x31F0, 0x31FF, // Katakana Phonetic Extensions
		0xFF00, 0xFFEF  // Half-width characters
	};
	static ImWchar fullRanges[IM_ARRAYSIZE(baseRanges) + IM_ARRAYSIZE(accumulativeOffsetsFrom0x4E00) * 2 + 1] = { 0 };
	if (!fullRanges[0]) {
		memcpy(fullRanges, baseRanges, sizeof(baseRanges));
		UnpackAccumulativeOffsetsIntoRanges(0x4E00, accumulativeOffsetsFrom0x4E00, IM_ARRAYSIZE(accumulativeOffsetsFrom0x4E00), fullRanges + IM_ARRAYSIZE(baseRanges));
	}
	return &fullRanges[0];
}

// 来自 https://github.com/flyinghead/flycast/blob/541544292a3d051839672ffa7bd4524a3e1c1c51/core/rend/gui_util.cpp#L523
const ImWchar* OverlayHelper::GetGlyphRangesChineseTraditionalOfficial() noexcept {
	// Store all official characters for Traditional Chinese.
	// Sourced from https://https://en.wikipedia.org/wiki/List_of_Graphemes_of_Commonly-Used_Chinese_Characters
	// (Stored as accumulative offsets from the initial unicode codepoint 0x4E00. This encoding is designed to helps us compact the source code size.)
	static const short accumulativeOffsetsFrom0x4E00[] =
	{
		0,1,2,5,1,1,1,2,3,1,3,1,1,2,1,5,1,3,4,5,2,5,6,1,2,8,2,6,2,1,1,3,1,3,2,1,4,1,1,10,10,11,4,4,2,3,1,2,3,1,2,1,4,2,3,1,2,3,1,1,2,3,1,1,1,12,6,1,
		2,1,2,1,3,1,2,7,1,1,1,1,1,5,1,4,1,1,11,2,1,3,5,1,1,2,2,8,1,3,2,1,1,4,4,22,1,4,2,2,2,2,1,6,3,1,1,5,1,1,1,1,3,1,2,2,2,1,1,1,2,3,6,3,3,1,3,2,6,
		4,4,3,2,3,2,2,7,5,2,17,1,6,1,9,3,1,1,6,4,1,1,1,6,1,2,3,1,1,1,1,13,1,4,5,2,4,2,6,3,2,1,1,2,2,1,2,2,2,1,1,5,2,2,2,1,2,1,1,1,2,9,6,7,4,2,3,2,1,
		6,5,2,9,15,1,1,1,6,3,5,8,4,5,2,1,9,10,1,5,1,2,2,4,3,7,10,2,4,1,4,9,2,2,7,3,4,4,2,5,2,2,4,1,7,2,2,4,7,2,9,8,5,5,4,1,2,1,1,1,1,1,1,2,1,1,4,1,2,
		1,2,5,6,3,2,1,1,2,1,1,1,3,4,1,1,1,4,4,9,1,3,4,1,3,11,2,2,1,7,4,6,1,6,9,5,1,1,15,1,3,1,15,1,2,3,2,1,1,3,3,1,2,3,1,1,2,4,3,1,5,6,7,4,1,1,1,3,2,
		6,1,1,2,1,6,2,4,3,1,1,1,1,6,2,5,1,1,12,1,5,3,2,1,2,6,2,4,4,1,1,4,4,10,4,1,3,6,1,1,1,18,3,2,4,2,9,3,2,1,1,2,2,1,1,3,2,15,2,3,3,3,1,1,5,1,2,5,
		2,1,5,1,1,2,4,3,1,2,7,5,2,8,5,1,1,1,2,2,2,1,1,1,7,1,1,1,3,3,2,2,2,1,5,1,5,2,2,1,2,2,2,1,1,2,4,5,22,5,6,8,5,9,8,5,1,1,1,2,7,2,1,2,2,4,3,1,1,1,
		1,2,1,1,1,1,1,1,1,1,1,1,1,2,3,4,5,2,1,2,2,1,2,1,1,1,1,1,1,1,9,2,1,1,1,6,1,2,2,2,1,3,2,2,3,1,2,1,2,2,2,1,3,2,2,4,2,18,6,9,2,2,1,1,1,3,1,1,3,4,
		2,5,1,2,2,2,3,1,4,12,1,1,1,1,1,1,3,2,2,5,3,2,3,1,1,2,3,1,1,5,19,4,1,2,1,1,3,1,4,8,2,5,5,1,2,7,4,19,5,2,1,2,2,4,1,6,3,2,1,2,4,5,6,1,6,2,1,2,2,
		1,1,1,4,17,1,2,2,2,1,1,3,2,1,1,9,4,2,2,1,2,8,3,2,2,3,1,1,8,10,1,1,2,5,3,2,7,2,3,2,2,1,1,3,7,8,6,1,2,6,2,1,4,7,2,1,4,4,10,5,1,1,2,2,2,3,2,4,
		15,5,4,2,9,2,1,3,1,1,1,1,3,2,3,4,1,7,5,2,7,1,6,16,3,6,6,2,1,5,4,1,1,6,1,1,2,5,9,1,3,2,4,6,6,1,9,9,5,3,2,5,1,3,2,7,9,4,1,2,1,3,11,2,7,3,3,1,
		1,1,1,16,3,2,3,1,13,5,6,1,8,21,2,1,11,21,8,3,6,11,1,23,2,1,8,3,1,27,3,6,5,1,1,3,1,21,2,5,3,3,1,2,4,4,9,10,4,5,2,3,2,5,9,9,2,1,9,6,5,11,3,4,
		2,10,2,2,3,1,5,1,5,5,2,1,3,10,1,3,18,6,1,3,1,2,3,3,2,1,2,2,1,1,2,1,3,6,1,6,6,3,1,1,5,1,1,1,3,1,2,1,2,6,2,5,2,1,4,5,1,2,2,1,4,5,1,1,6,3,5,1,3,
		3,4,1,5,1,1,3,6,1,4,6,2,3,8,4,1,2,3,1,1,1,1,4,2,2,7,2,1,2,2,2,15,4,2,2,9,5,2,5,3,1,3,1,3,2,4,13,6,4,1,5,3,1,16,8,4,4,13,8,19,8,1,15,8,1,10,1,
		3,1,7,3,10,1,1,9,2,3,3,12,5,1,14,2,1,17,7,6,6,4,4,8,16,1,2,1,1,2,1,2,2,1,2,4,1,5,2,5,1,2,2,3,2,3,2,3,1,2,2,1,1,2,1,3,8,1,1,1,1,1,6,1,1,1,1,8,
		2,3,1,1,1,3,6,3,2,1,1,1,5,4,2,1,11,1,2,1,2,1,1,1,1,1,2,1,2,7,1,2,2,7,3,1,2,1,1,1,1,2,1,1,2,5,4,10,8,5,6,1,1,1,2,2,1,1,1,4,1,2,3,2,1,1,1,1,4,
		7,4,2,2,1,7,3,2,8,19,4,1,3,13,8,2,6,2,4,1,33,15,1,1,3,2,1,6,5,2,9,1,7,3,3,2,1,2,2,7,7,35,4,25,27,3,22,29,2,1,16,5,2,2,7,1,3,1,3,1,1,1,3,3,3,
		1,1,1,3,6,1,4,1,3,6,5,4,1,2,2,1,2,8,6,2,6,3,1,1,5,3,5,7,8,1,2,4,4,3,1,8,7,1,1,2,2,1,1,1,1,1,1,9,8,6,1,1,3,2,4,6,1,4,2,8,1,1,1,6,3,1,6,1,1,9,
		3,4,3,2,1,2,1,9,7,3,1,3,5,2,3,4,2,5,2,2,1,1,2,1,3,4,7,1,2,4,4,4,2,5,10,2,4,2,9,2,4,5,2,1,4,1,1,1,1,3,1,6,2,3,3,1,1,4,2,1,2,1,1,4,1,1,5,1,1,5,
		3,7,1,1,2,2,7,2,2,4,6,2,7,1,9,1,1,1,4,3,11,6,4,7,1,2,15,1,3,2,1,1,7,3,1,4,2,1,2,5,2,4,14,3,7,3,5,4,9,1,1,1,3,1,1,1,1,1,2,1,15,5,1,4,3,1,7,
		2,4,5,1,3,3,2,10,2,1,1,2,3,1,1,8,1,5,6,4,3,2,2,3,1,1,5,10,1,2,1,2,3,1,1,5,1,7,1,5,1,6,5,1,1,3,1,3,4,13,10,1,5,3,1,3,1,1,1,7,3,2,3,2,3,1,4,1,
		3,3,2,3,3,1,5,2,4,8,4,2,1,3,6,10,3,2,2,1,6,4,8,4,5,1,1,1,3,22,3,12,3,1,1,1,2,2,3,1,8,2,2,1,1,2,1,1,3,1,4,1,4,2,1,8,4,2,2,1,1,3,7,1,1,1,6,1,1,
		2,2,1,4,1,1,4,3,8,10,1,1,4,3,3,3,2,1,1,4,5,1,7,1,1,2,1,1,1,16,3,1,5,4,4,3,1,2,3,2,2,1,1,1,2,1,1,3,2,1,1,2,1,1,1,1,1,1,16,1,1,1,2,2,1,3,5,1,1,
		1,2,6,1,1,8,5,18,2,1,4,11,3,1,4,4,3,5,1,1,5,18,1,1,2,6,1,4,1,4,5,3,1,4,1,3,3,3,4,2,1,2,5,1,1,1,2,2,1,1,1,2,20,6,3,4,2,1,2,4,4,1,6,2,6,1,3,1,
		6,25,2,4,1,2,1,5,2,12,2,1,9,4,3,1,19,1,2,4,7,8,2,6,9,1,1,13,1,8,2,1,2,5,4,6,1,4,2,1,1,1,2,2,9,1,3,2,1,2,1,2,3,1,2,1,4,2,4,2,6,1,5,1,5,4,1,1,
		2,6,1,3,2,6,9,5,4,1,3,1,6,1,6,1,1,3,7,3,2,3,1,6,3,5,2,2,5,1,1,1,4,1,4,1,3,6,6,2,1,2,1,10,1,4,9,1,6,2,3,3,2,3,1,2,4,1,3,1,7,2,3,1,4,4,6,1,2,1,
		7,1,11,3,1,2,1,3,1,4,9,8,4,1,5,2,1,4,1,11,1,5,2,1,5,2,19,1,6,3,3,11,3,7,2,2,6,1,1,4,2,4,13,1,1,8,5,1,11,6,3,3,6,5,13,3,13,3,4,3,6,6,4,2,1,1,
		3,1,1,3,2,1,1,3,5,1,2,2,7,1,2,4,2,2,7,1,1,2,1,1,1,1,3,3,1,8,9,3,5,1,1,1,5,6,2,1,14,2,1,1,2,2,2,7,1,8,2,6,1,5,2,5,1,18,2,5,2,12,11,1,1,2,1,6,
		2,9,4,3,3,2,2,1,1,5,5,20,4,10,8,1,14,1,3,1,3,2,1,2,1,2,4,4,1,2,1,34,9,2,2,2,1,13,4,6,2,3,5,1,5,2,1,3,2,15,5,2,2,5,3,2,1,2,5,1,3,4,7,4,3,4,1,
		11,8,1,4,30,26,9,1,6,4,2,8,3,2,8,2,2,9,4,14,1,6,1,10,2,5,1,6,3,4,6,10,1,1,3,3,21,11,10,4,1,8,7,2,6,5,1,2,2,18,3,1,1,3,7,3,4,13,1,6,2,1,9,21,
		4,16,8,6,10,3,4,5,3,7,1,5,11,7,1,2,8,22,9,6,12,10,1,2,15,8,3,1,9,2,3,2,2,15,2,1,1,1,1,1,1,3,8,5,1,1,2,4,4,3,3,1,12,2,12,10,1,3,3,2,3,2,3,1,5,
		1,5,2,2,3,1,1,3,4,16,4,14,13,5,1,1,2,3,5,4,4,1,2,1,1,3,3,1,3,2,4,6,2,1,1,14,5,2,6,1,1,1,1,7,2,6,2,8,3,1,3,2,2,3,4,4,2,4,3,2,16,3,3,2,5,1,2,
		1,1,1,1,2,3,1,4,1,2,7,2,2,4,6,1,1,2,3,8,1,2,24,12,4,3,7,4,1,7,1,4,5,2,1,3,24,1,12,3,1,2,2,6,3,1,15,1,1,3,2,5,2,25,1,3,3,3,4,8,1,1,1,4,1,5,1,
		6,1,1,4,3,3,4,2,1,3,3,2,2,2,2,1,1,10,20,1,1,2,3,1,2,1,1,1,3,3,1,2,3,2,4,2,4,5,7,3,7,2,2,3,12,7,1,26,7,6,2,4,1,5,3,5,5,7,4,2,6,2,1,2,4,1,5,2,
		1,24,3,3,2,10,1,2,1,4,9,4,1,1,11,2,1,6,1,1,1,5,1,1,5,6,1,18,3,4,3,9,2,7,1,2,8,2,2,4,4,2,2,6,9,10,3,3,10,2,6,7,1,1,1,21,3,4,1,1,3,7,1,3,2,9,4,
		8,3,2,4,2,4,5,1,2,2,9,8,14,14,5,7,11,8,5,6,2,4,1,13,4,4,3,4,18,1,1,1,1,4,5,2,14,2,5,9,1,6,5,21,4,12,1,15,1,7,5,10,6,19,3,2,11,3,2,6,1,1,1,
		1,1,3,2,15,7,6,10,5,6,9,4,5,8,5,5,1,4,1,5,2,2,3,4,3,3,6,1,1,5,1,1,6,7,11,7,3,11,13,2,2,1,3,2,3,1,2,1,1,1,2,1,2,6,1,1,4,6,4,2,1,2,2,2,1,1,1,5,
		2,6,3,2,5,4,3,1,3,14,4,5,7,5,5,3,17,2,2,10,2,7,2,7,1,8,14,1,1,3,1,25,3,2,1,9,4,11,2,1,7,1,5,1,9,2,7,17,8,2,3,2,1,2,1,5,4,3,2,2,11,9,10,2,7,1,
		4,4,5,10,3,19,13,1,16,5,2,1,3,1,24,3,1,2,2,9,1,2,4,5,2,20,4,1,1,1,2,1,4,1,5,1,5,1,19,8,17,7,3,1,9,13,13,5,13,4,2,1,3,16,1,13,8,9,3,2,2,3,3,3,
		1,2,1,2,1,1,3,1,1,1,4,1,20,3,5,5,1,2,1,5,3,1,1,3,1,5,6,2,14,1,3,1,3,1,2,8,1,3,7,1,6,7,1,2,4,3,1,1,7,2,3,10,1,3,1,2,3,4,1,13,1,2,1,6,5,1,1,8,
		2,2,3,3,12,1,1,3,3,2,11,4,10,4,6,6,4,2,9,1,3,4,3,2,3,1,6,3,1,1,1,4,2,2,1,1,6,5,3,4,20,2,4,6,5,3,1,3,2,2,3,1,4,2,7,1,2,1,2,2,1,1,2,3,4,1,3,2,
		4,1,3,2,3,8,2,20,1,8,1,13,1,1,2,2,2,2,15,12,1,2,3,2,2,1,2,3,1,13,4,1,1,5,3,5,2,3,13,1,1,5,2,3,2,1,3,3,8,2,2,8,12,4,3,1,1,6,1,2,4,4,1,1,4,10,
		5,10,1,7,9,8,2,6,3,2,2,4,11,26,14,1,3,13,13,3,2,3,6,1,7,8,2,7,3,7,2,2,3,4,5,1,5,5,5,14,4,3,5,3,3,7,13,11,13,4,1,1,14,4,2,1,5,1,1,1,7,5,1,1,3,
		3,1,1,1,5,3,5,13,5,2,12,1,1,23,1,3,4,3,9,3,1,1,1,1,8,2,6,1,13,4,1,2,1,2,18,5,5,3,3,2,1,6,6,2,3,1,14,3,6,4,1,1,2,1,7,5,1,1,9,10,1,7,2,9,2,3,
		1,5,2,3,4,10,3,1,1,1,7,1,9,1,4,1,11,10,1,2,1,2,1,14,6,1,3,2,8,2,7,3,1,3,2,7,11,8,2,3,2,6,2,4,26,3,2,2,2,1,2,2,2,10,21,2,20,4,5,1,2,6,4,12,4,
		3,12,1,3,2,1,2,16,8,3,5,14,7,9,6,17,3,2,4,3,1,12,1,5,1,1,4,9,1,18,1,4,8,2,4,1,22,9,3,2,8,6,12,2,2,5,3,1,11,1,11,1,3,3,2,1,1,2,5,8,12,3,2,2,
		2,1,2,2,1,1,2,3,4,1,2,2,1,1,1,4,1,1,9,3,1,1,3,6,3,4,2,1,1,2,10,5,9,3,1,4,2,6,3,1,7,8,8,6,2,2,9,2,2,2,9,2,3,1,1,2,1,3,2,1,2,1,1,8,3,8,6,2,3,1,
		2,3,5,1,3,3,5,7,13,9,4,6,8,8,3,3,1,5,6,1,3,2,2,1,14,1,5,4,3,8,1,1,2,6,6,3,1,5,10,3,4,3,6,154,2,2,3,7,4,8,4,1,10,10,1,4,2,2,3,2,2,12,3,2,2,2,
		6,6,4,5,1,4,1,6,3,4,2,1,4,2,2,4,7,2,4,2,1,10,1,1,8,7,1,2,6,1,1,1,4,1,2,2,1,6,1,3,2,3,2,1,1,3,23,3,7,2,7,4,12,2,2,4,17,1,1,1,1,3,1,6,1,1,5,1,
		1,1,2,2,1,7,3,2,2,1,2,4,1,3,4,1,1,4,2,1,2,6,9,9,2,8,4,1,3,3,3,1,8,3,1,2,1,4,5,5,3,1,2,2,12,13,6,2,4,2,8,5,8,5,3,2,1,3,1,16,1,5,3,2,1,2,5,1,1,
		5,1,8,2,5,11,1,1,1,3,8,1,10,7,3,1,1,1,2,1,3,3,4,2,9,2,5,4,2,2,1,2,3,6,1,6,1,1,2,2,2,3,2,1,1,1,2,1,3,2,2,7,1,2,1,3,6,2,1,1,9,1,1,2,14,17,1,
		13,8,1,2,1,4,8,13,2,5,7,4,2,6,7,1,4,2,6,2,2,20,1,1,1,3,4,3,1,4,2,1,1,10,16,1,1,1,1,4,14,20,6,1,2,1,1,2,1,7,3,6,1,5,1,2,2,35,1,3,1,13,1,4,4,
		1,3,2,6,2,2,9,18,4,4,5,2,16,4,9,6,1,1,1,2,4,5,6,1,6,1,1,1,1,30,5,4,3,4,1,12,14,4,6,2,3,3,2,1,5,4,2,11,14,9,3,2,20,6,4,3,1,4,2,3,2,6,2,25,2,
		35,2,1,3,3,7,2,9,1,16,6,6,1,15,15,1,1,3,17,6,3,10,3,8,10,3,1,5,1,6,19,4,2,6,8,7,1,4,1,15,1,1,11,1,3,1,6,9,19,11,7,15,2,4,1,6,1,2,1,8,4,4,2,8,
		17,2,7,16,1,5,1,5,2,5,10,6,1,4,9,5,2,4,5,9,12,2,3,2,2,1,4,1,11,2,3,2,2,6,3,15,7,4,13,9,2,2,7,6,2,12,2,2,10,1,10,17,1,3,9,8,7,1,5,6,2,3,6,1,
		26,3,3,9,10,8,2,5,1,10,2,1,1,14,5,3,2,5,12,1,6,4,2,2,2,4,1,1,5,3,5,7,10,1,6,3,2,5,4,8,13,6,16,1,8,5,5,1,3,1,3,1,2,2,7,11,1,4,1,4,5,5,9,2,1,7,
		5,6,5,1,7,6,3,8,1,18,9,1,4,6,5,3,13,2,2,3,5,4,4,3,16,4,2,6,8,3,3,18,17,17,4,8,2,1,5,2,2,2,1,4,2,1,1,1,3,2,2,4,2,5,3,4,3,6,1,6,5,10,4,1,6,3,
		2,2,1,3,3,2,1,1,1,2,1,1,1,6,3,9,2,5,1,4,2,2,3,6,2,1,2,1,1,1,2,2,2,4,2,10,3,3,2,3,2,2,2,5,4,6,10,1,4,2,1,3,6,1,2,4,2,1,1,2,6,4,9,2,2,2,3,8,4,
		13,8,8,3,2,1,9,2,2,10,6,3,1,4,3,6,3,10,8,1,3,4,157,8,2,5,2,1,3,2,2,4,1,5,7,1,8,1,1,13,1,8,7,3,1,6,10,1,2,1,1,5,1,1,1,1,1,3,3,1,1,2,1,1,3,1,
		1,2,1,1,1,1,1,1,2,1,2,7,1,1,9,2,2,2,1,1,2,4,2,1,7,6,2,1,8,3,2,1,2,2,4,3,5,73,2,1,4,2,3,3,1,3,10,4,5,11,4,6,4,5,11,1,10,8,5,1,2,3,9,1,2,2,2,
		7,2,5,4,7,2,19,1,13,2,3,7,1,1,6,3,1,4,9,2,4,1,1,1,14,6,4,1,2,6,6,4,4,2,5,1,3,2,2,1,3,4,16,9,1,1,1,5,8,6,10,1,1,1,5,2,7,4,25,3,1,2,5,6,1,8,1,
		1,1,6,1,1,2,7,3,1,3,2,9,3,3,1,3,2,1,4,4,1,6,11,2,58,1,3,4,3,2,5,1,1,1,1,1,16,2,1,9,3,3,14,2,1,1,4,1,2,3,4,3,1,1,1,3,3,1,2,2,1,7,2,1,4,1,1,1,
		2,1,1,2,1,1,1,2,1,11,3,1,3,3,4,2,3,1,5,3,1,2,1,1,1,1,2,1,1,3,1,3,2,2,3,5,1,4,1,4,2,1,2,1,2,2,1,2,1,1,1,2,3,3,5,1,1,4,13,1,3,2,2,7,4,3,9,9,4,
		19,7,5,8,8,5,7,9,7,14,6,3,1,24,1,1,1,1,5,5,12,2,4,1,2,9,2,1,11,4,2,2,7,10,2,5,8,1,14,6,1,6,2,2,1,1,1,1,1,1,6,1,4,1,6,3,1,14,20,4,1,2,4,1,9,
		5,17,3,1,6,2,11,6,6,4,7,2,28,5,14,3,2,4,16,7,4,2,2,1,5,4,13,18,6,3,11,4,8,12,8,2,6,2,4,2,3,4,4,3,20,1,2,14,10,7,9,9,4,8,10,2,12,12,5,16,5,9,
		5,1,1,4,3,2,1,27,6,21,22,4,1,2,3,2,10,13,1,14,3,13,2,10,1,1,1,248,9,2,1,6,2,4,2,1,1,1,4,9,2,1,1,3,1,4,4,1,9,11,2,2,1,1,4,4,2,6,5,1,58,5,9,4,
		3,1,9,4,1,4,7,1,1,3,11,1,5,1,1,1,6,6,2,1,2,1,1,1,5,8,1,4,1,2,1,6,1,3,1,2,1,11,1,2,7,3,4,3,5,1,3,1,1,1,2,2,1,1,8,1,3,2,1,2,4,1,5,2,5,3,4,1,2,
		2,5,4,2,1,2,4,1,1,2,2,3,6,2,9,3,8,6,1,4,1,4,2,4,10,4,5,1,2,2,1,1,4,2,1,4,7,2,6,9,6,2,2,9,8,3,3,7,20,2,3,5,1,7,9,17,6,2,1,5,4,2,1,1,2,1,2,4,
		4,1,1,1,4,1,9,3,9,3,7,1,1,2,11,6,1,1,1,9,3,3,9,4,4,1,1,55,7,2,2,3,4,2,8,23,4,3,5,2,1,3,2,3,2,8,1,1,5,2,4,1,2,4,2,1,5,3,3,3,7,13,8,1,1,6,12,
		1,10,2,56,3,12,3,4,1,1,3,2,1,13,15,1,1,3,4,2,2,2,3,11,4,14,2,13,8,3,18,5,7,7,2,3,2,16,2,3,1,4,3,3,5,62,7,1,7,1,4,19,3,1,1,4,14,7,1,1,12,8,3,
		7,13,8,3,2,1,9,11,5,1,2,1,10,5,4,2,21,8,26,26,3,27,1,30,21,16,6,18,8,4,10,3,22,2,1,32,1,109,4,10,1,2,16,3,12,6,8,3,2,19,4,18,12,3,1,9,2,6,
		23,38,5,14,17,4,14,20,1,32,4,87,4,3,1,2,12,7,1,4,6,2,6,4,1,10,7,1,1,1,5,10,1,1,2,3,4,3,1,1,1,2,8,7,5,3,16,1,6,5,2,4,7,12,8,7,3,12,1,7,13,2,
		2,3,4,2,6,5,22,3,4,8,
	};
	static ImWchar baseRanges[] = // not zero-terminated
	{
		0x0020, 0x00FF, // Basic Latin + Latin Supplement
		0x2000, 0x206F, // General Punctuation
		0x3000, 0x30FF, // CJK Symbols and Punctuations, Hiragana, Katakana
		0x31F0, 0x31FF, // Katakana Phonetic Extensions
		0xFF00, 0xFFEF  // Half-width characters
	};
	static ImWchar fullRanges[IM_ARRAYSIZE(baseRanges) + IM_ARRAYSIZE(accumulativeOffsetsFrom0x4E00) * 2 + 1] = { 0 };
	if (!fullRanges[0]) {
		memcpy(fullRanges, baseRanges, sizeof(baseRanges));
		UnpackAccumulativeOffsetsIntoRanges(0x4E00, accumulativeOffsetsFrom0x4E00, IM_ARRAYSIZE(accumulativeOffsetsFrom0x4E00), fullRanges + IM_ARRAYSIZE(baseRanges));
	}
	return &fullRanges[0];
}

static uint32_t GetSeed(const std::vector<const EffectDesc*>& effectDescs) noexcept {
	uint32_t result = 0;
	for (const EffectDesc* effectDesc : effectDescs) {
		result ^= (uint32_t)std::hash<std::string>()(effectDesc->name);
	}
	return result;
}

SmallVector<uint32_t> OverlayHelper::GenerateTimelineColors(const std::vector<const EffectDesc*>& effectDescs) noexcept {
	const uint32_t nEffect = (uint32_t)effectDescs.size();
	uint32_t totalColors = nEffect > 1 ? nEffect : 0;
	for (uint32_t i = 0; i < nEffect; ++i) {
		uint32_t nPass = (uint32_t)effectDescs[i]->passes.size();
		if (nPass > 1) {
			totalColors += nPass;
		}
	}

	if (totalColors == 0) {
		return {};
	}

	constexpr uint32_t nColors = (uint32_t)std::size(TIMELINE_COLORS);

	std::default_random_engine randomEngine(GetSeed(effectDescs));
	SmallVector<uint32_t> result;

	if (totalColors <= nColors) {
		result.resize(nColors);
		for (uint32_t i = 0; i < nColors; ++i) {
			result[i] = i;
		}
		std::shuffle(result.begin(), result.end(), randomEngine);

		result.resize(totalColors);
	} else {
		// 相邻通道颜色不同，相邻效果颜色不同
		result.resize(totalColors);
		std::uniform_int_distribution<uint32_t> uniformDst(0, nColors - 1);

		if (nEffect <= nColors) {
			if (nEffect > 1) {
				// 确保效果的颜色不重复
				std::array<uint32_t, nColors> effectColors{};
				for (uint32_t i = 0; i < nColors; ++i) {
					effectColors[i] = i;
				}
				std::shuffle(effectColors.begin(), effectColors.end(), randomEngine);

				uint32_t i = 0;
				for (uint32_t j = 0; j < nEffect; ++j) {
					result[i] = effectColors[j];
					++i;

					uint32_t nPass = (uint32_t)effectDescs[j]->passes.size();
					if (nPass > 1) {
						i += nPass;
					}
				}
			}
		} else {
			// 仅确保与前一个效果颜色不同
			uint32_t prevColor = std::numeric_limits<uint32_t>::max();
			uint32_t i = 0;
			for (uint32_t j = 0; j < nEffect; ++j) {
				uint32_t c = uniformDst(randomEngine);
				while (c == prevColor) {
					c = uniformDst(randomEngine);
				}

				result[i] = c;
				prevColor = c;
				++i;

				uint32_t nPass = (uint32_t)effectDescs[j]->passes.size();
				if (nPass > 1) {
					i += nPass;
				}
			}
		}

		// 生成通道的颜色
		size_t idx = 0;
		for (uint32_t i = 0; i < nEffect; ++i) {
			uint32_t nPass = (uint32_t)effectDescs[i]->passes.size();

			if (nEffect > 1) {
				++idx;

				if (nPass == 1) {
					continue;
				}
			}

			for (uint32_t j = 0; j < nPass; ++j) {
				uint32_t c = uniformDst(randomEngine);

				if (i > 0 || j > 0) {
					uint32_t prevColor = (i > 0 && j == 0) ? result[idx - 2] : result[idx - 1];

					if (j + 1 == nPass && i + 1 != nEffect && effectDescs[(size_t)i + 1]->passes.size() == 1) {
						// 当前效果的最后一个通道且下一个效果只有一个通道
						uint32_t nextColor = result[idx + 1];
						while (c == prevColor || c == nextColor) {
							c = uniformDst(randomEngine);
						}
					} else {
						while (c == prevColor) {
							c = uniformDst(randomEngine);
						}
					}
				}

				result[idx] = c;
				++idx;
			}
		}
	}

	return result;
}


}
